package gold.digger;

import gold.utils.InputUtil;
import gold.vo.ListNode;

import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * Created by fanzhenyu02 on 2021/12/10.
 * common problem solver template.
 */
public class LCJZOF078 {
    public long startExecuteTime = System.currentTimeMillis();


    /**
     * Definition for singly-linked list.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode() {}
     *     ListNode(int val) { this.val = val; }
     *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
     * }
     */

    /**
     * k == lists.length
     * 0 <= k <= 10^4
     * 0 <= lists[i].length <= 500
     * -10^4 <= lists[i][j] <= 10^4
     * lists[i] 按 升序 排列
     * lists[i].length 的总和不超过 10^4
     */

    class Solution {
        public ListNode mergeKLists(ListNode[] nodeList) {
            ListNode ans = new ListNode(-1), cur = ans;
            PriorityQueue<ListNode> pq = new PriorityQueue<>(new Comparator<ListNode>() {
                @Override
                public int compare(ListNode o1, ListNode o2) {
                    return o1.val - o2.val;
                }
            });

            int len = nodeList.length;
            for (int i = 0; i < len; i++) {
                if (null != nodeList[i]) {
                    pq.add(nodeList[i]);
                }
            }

            while (!pq.isEmpty()) {
                ListNode temp = pq.poll();
                cur.next = temp;
                cur = temp;
                if (null != temp.next) {
                    pq.add(temp.next);
                }
            }

            return ans.next;
        }
    }

    public void run() {


//        输入：lists = [[1,4,5],[1,3,4],[2,6]]
//        输出：[1,1,2,3,4,4,5,6]
        System.out.println(new Solution().mergeKLists(new ListNode[]{ListNode.createListFromArrayString("[1,4,5]"), ListNode.createListFromArrayString("[1,3,4]"), ListNode.createListFromArrayString("[2,6]")}));


    }

    public static void main(String[] args) throws Exception {
        LCJZOF078 an = new LCJZOF078();
        an.run();

        System.out.println("\ncurrent solution total execute time: " + (System.currentTimeMillis() - an.startExecuteTime) + " ms.");
    }
}
